package usually;

import javafx.scene.effect.SepiaTone;

import java.util.HashSet;
import java.util.Set;

//81. 搜索旋转排序数组 II
public class Num81_search {
    public boolean search(int[] nums, int target) {
        /**
         * set集合
         */
//        Set<Integer> set = new HashSet<>();
//        for (int i : nums){
//            if (!set.contains(i))set.add(i);
//        }
//        return set.contains(target);
        /**
         * 二分查找
         */

        //边界条件
        int n = nums.length;
        if (n == 0)return false;
        if (n == 1)return nums[0] == target;
        int l = 0, r = n - 1;
        while (l <= r){

            int mid = l + (r - l) / 2;
            //判断
            if (nums[mid] == target)return true;
            //去除重复值
            if (nums[l] == nums[mid] && nums[r] == nums[mid]){
                l++;
                r--;
            }else if (nums[l] <= nums[mid]){
                //前半部分有序，去前半部分找
                if (nums[l] <= target && target <= nums[mid] ){
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }else {
                if (nums[r] >= target && target >= nums[mid]){
                    l = mid + 1;
                }else {
                    r = mid - 1;
                }
            }
        }
        return false;

    }
}
